package com.example.androidtraining_ahut2020.proj.util;

import java.util.Arrays;
import java.util.List;
import java.util.Vector;

public class BruteSearcherDFSImp implements Searcher {


    public static void main(String[] args) {
        System.out.println(new BruteSearcherDFSImp().search(new int[]{1, 5, 5, 5}));
        // System.out.println(search(new int[]{1, 4, 2, 3}));
        //  System.out.println(search(new int[]{1, 1, 1, 1}));
    }


    /**
     * 确定搜索器的实现v1.0
     * 枚举运算符的种类,构造出后缀表达式
     *
     * @param arr2
     * @return
     */
    public List<String> search(int[] arr2) {
        List<String> ans = new Vector<String>();
        for (int i = 0; i < 7; i++) ans.add(new String(""));
        for (int x = 0; x < 4; x++)
            for (int y = 0; y < 4; y++)
                for (int z = 0; z < 4; z++) {
                    List<String> exp = new Vector<>();
                    exp.add(OPERATORS[x]);
                    exp.add(OPERATORS[y]);
                    exp.add(OPERATORS[z]);
                    for (int e : arr2) exp.add(Integer.toString(e));
                    dfs(0, exp, ans);
                    if (flag) {

                        return ans;
                    }
                }
        return null;
    }

    static int n = 7;
    static int[] book = new int[n];
    static String[] arr = new String[n];
    public static boolean flag = false;

    static void dfs(int k, List<String> exp, List<String> ans) {
        if (flag) return;
        if (k >= n) {
            if (Math.abs(PostExpression.eval(arr) - TARGET) < EPS) {
                flag = true;
                for (int i = 0; i < n; i++) {
                    ans.set(i, arr[i]);
                }
            }
            return;
        }
        for (int i = 0; i < n; i++) {
            if (book[i] == 1) continue;
            arr[k] = exp.get(i);
            book[i] = 1;
            dfs(k + 1, exp, ans);
            book[i] = 0;
        }
    }

    public static void reset() {
        Arrays.fill(book, 0);
        flag = false;
    }
}
